The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The recent development of a theory of computational-geometric sampling has revolutionized the design of geometric algorithms, and led to the solution of some of the most outstanding problems in the field. Much of this development owes to the interplay between computational geometry and discrepancy theory. This talk will discuss some intriguing aspects of this development, including the use of data...
A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space [1l]. In this paper we consider the dynamic version of the motion planning problem...
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually “see” an evader that is unpredictable, has unknown initial position, and is capable of moving arbitrarily fast. This problem was first introduced by Suzuki and Yamashita. Our study of this problem is motivated in part by robotics applications, such as surveillance with a mobile...
Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of the points. When the points in S move with pseudo-algebraic motions, these structures process O(n2+ε) events. We also give constructions showing that μ(n2) combinatorial changes are...
In this paper we consider the problem of finding a core of limited length in a tree. A core is a path, which minimizes the sum of the distances to all nodes in the tree. This problem has been examined under different constraints on the tree and on the set of paths, from which the core can be chosen. For all cases, we present linear or almost linear time algorithms, which improves the previous results...
We study the bipartite crossing number problem. When the minimum degree and the maximum degree of the graph are close to each other, we derive two polynomial time approximation algorithms for solving this problem, with approximation factors, O(log2n), and O(log n log log n), from the optimal, respectively, where n is the number of vertices. This problem had been known to be NP-hard, but...
We define and study a combinatorial problem called WEIGHTED DIAGNOSTIC COVER (WDC) that models the use of a laboratory technique called genotyping in the diagnosis of a important class of chromosomal aberrations. An optimal solution to WDC would enable us to define a genetic assay that maximizes the diagnostic power for a specified cost of laboratory work. We develop approximation algorithms for WDC...
The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. By using a data structure that...
In the precedence-constrained traveling salesman problem (PTSP) we are given a partial order on n nodes, each of which is labeled by one of k points in a metric space. We are to find a visit order consistent with the precedence constraints that minimizes the total cost of the corresponding path in the metric space. We give negative results on approximability by relating the problem to the Shortest...
We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + √8 ≈ 5.828 for the deterministic version, and 3.31/ln 2.155 ≈ 4.311 for its randomized variant, improving the previous competitive ratios of 8 and 2e ≈ 5.436. We also prove lower bounds of 2.4380 on the competitive ratio of deterministic...
For sequence alignments (which can be viewed simply as rectangular arrays of characters), a frequent need is to identify regions, each consisting of a run of consecutive columns, that have some particular property. The 1-mismatch problem is to locate all maximal regions in a given alignment for which there exists a (not necessarily unique) “center” sequence such that inside the region alignment rows...
Efficient geometric algorithms are given for optimization problems arising in layered manufacturing, where a 3D object is built by slicing its CAD model into layers and manufacturing the layers successively. The problems considered include minimizing the degree of stair-stepping on the surfaces of the manufactured object, minimizing the volume of the so-called support structures used, and minimizing...
Construction heuristics for the traveling salesman problem (TSP), with the 2-Opt applied as a postprocess, are studied with respect to their tour lengths and computation times. In this study, the “2-Opt dependency,” which indicates how the performance of the 2-Opt depends on the initial tours built by the construction heuristics, is analyzed. In accordance with the analysis, we devise a new construction...
A myriad of textual problems have been considered in the pattern matching field with many non-trivial results. Nevertheless, surprisingly little work has been done on the natural combination of pattern matching and hypertext. In contrast to regular text, hypertext has a nonlinear structure and the techniques of pattern matching for text cannot be directly applied to hypertext. Manber and Wu...
We present two new algorithms for on-line multiple approximate string matching. These are extensions of previous algorithms that search for a single pattern. The single-pattern version of the first one is based on the simulation with bits of a non-deterministic finite automaton built from the pattern and using the text as input. To search for multiple patterns, we superimpose their automata, using...
Computational Geometry has been a thriving research area for the past 20 years. During that time, the field has grown from a handful of researchers working on a small set of problems to a full-blown research area with multiple conferences and journals and many hundreds of researchers. The initial motivation for the field was to develop algorithms that would find application in practice in other fields...
This paper studies the problem of verifying the correctness of geometric structures. We design optimal checkers for convex polytopes in two and higher dimensions, and for various types of planar subdivisions, such as triangulations, Delaunay triangulations, and convex subdivisions. Our checkers are simpler and more general than the ones previously described in the literature. Their performance is...
In this paper we develop the concept of a polygon-offset distance function and show how to compute the respective nearest- and furthest-site Voronoi diagrams of point sites in the plane. We provide optimal deterministic O(n(log n + log m) + m)-time algorithms, where n is the number of points and m is the complexity of the underlying polygon, for computing compact representations of both diagrams.
The problem of scheduling independent jobs on m parallel machines in an online fashion was introduced by Graham in 1966. While the deterministic case of this problem has been studied extensively, little work has been done on the randomized case. For m = 2 an algorithm achieving a competitive ratio of 4/3 was found by Bartal, Fiat, Karloff and Vohra. These same authors show a matching lower bound....
Consider a set P of points in the plane sorted by χ-coordinate. A point p in P is said to be a proximate point if there exists a point q on the χ-axis such that p is the closest point to q over all points in P. The proximate points problem is to determine all proximate points in P. We propose optimal sequential and parallel algorithms for the proximate points problem. Our sequential algorithm runs...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.